package Hot100;



/**
 * 解题思路：
 *  本题数据量为1e5,如果通过模拟解题，即两层for循环，外层枚举左边界，内层枚举右边界，时间复杂度为O(n方)，超时
 *  采用双指针策略，左右指针指向两个边界，每次移动高度较小的那个
 *  每次移动较小高度的边界原因：首先，每次移动，两个边界的长度范围会降低
 *  如果移动的是高度较大的边界，则高度变化有两种情况：
 *     (1)新边界的高度比原来边界的高度低，若新边界比另一个边界的高度高，则较小值仍取另一边界；若新边界比另一边界的高度低，则两边界参与计算高度相较降低，不可能出现区域面积变大
 *     (2)新边界的高度比原来边界的高度高，因为在计算时取的是两个边界的最小值，由于替换的已是较大的边界，则在计算时两边界取到的较小值不会变化，但因为两个边界长度范围缩小，则面积钱少
 *  综上，若移动边界高度较大的那个，不会出现区域面积增大的情况
 *  如果移动边界较小的那个，虽然两个边界长度范围减少，但因为边界高度可能增加，则可能会出现更大的区域面积。
 */
public class L5 {
    public int maxArea(int[] height) {
        int area=-1;
        int l=0,r=height.length-1;
        while (l<r){
            int area_temp=Math.min(height[l],height[r])*(r-l);
            area=Math.max(area,area_temp);
            // 移动边界 移动高度较小的
            if (height[l]<=height[r]){
                l++;
            }else{
                r--;
            }
        }
        return area;
    }
}
